package com.xxd.algo.newcode.base01.class08;

public class Code07_Knapsack {


	// 重量  3 2 4 7
	// 价值  5 6 3 19
	// 11
	public static int getMaxValue(int[] w, int[] v, int bag) {
		return process(w, v, 0, 0, bag);
	}

	/**
	 * 背包问题 暴力递归
	 *
	 * @param w        物品
	 * @param v        价值
	 * @param index    前面已经决定过得索引
	 * @param alreadyW 背包已经使用的容量
	 * @param bag      背包的总容量
	 * @return 能装下的最大价值
	 */
	private static int process(int[] w, int[] v, int index, int alreadyW, int bag) {
		if (alreadyW > bag) {
			return -1;
		}

		if (index == w.length) {
			return 0;
		}

		// 不要
		int p1 = process(w, v, index + 1, alreadyW, bag);

		// 要
		int p2next = process(w, v, index + 1, alreadyW + w[index], bag);

		// 要了 可能这个东西他没法要啊，所以要有判断
		int p2 = -1;
		if (p2next != -1) {
			p2 = v[index] + p2next;
		}
		return Math.max(p1, p2);
	}

	public static void main(String[] args) {
		int[] weights = {3, 2, 4, 7};
		int[] values = {5, 6, 3, 19};
		int bag = 11;
		System.out.println(getMaxValue(weights, values, bag));
	}

}
